package com.demo300_最长递增子序列;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.TreeSet;

/**
 * 把 491题中的求递增子序列问题, 稍微转变一下.   把每次对结果的收集转变为对这个 集合中元素个数的一个大小比较,
 *
 * 并且求其最大值
 *
 * 这个版本超时了, 需要进行一个剪枝的操作 ~
 *
 * 所以这里是 包含最后一个元素的最长的递增子序列:
 *
 * 因为在这个for循环中, 每次只有这个  nums[i]>nums[j]的情况,我们才会去进行一个 取较大值.
 * 但是对于其他的情况,  就没有进行一个取值的比较,   所以 需要在每一轮循环结束后  进行一个比较取大值.
 *
 * dp[i] 的含义:  包含当前nums[i] 元素的最长子序列.  就是以当前 nums[i] 为序列尾部的子序列的最长长度.
 */
public class Solution_动态规划 {
    public static void main(String[] args) {
        int[] ints={1,3,6,7,9,4,10,5,6};
        int count = lengthOfLIS(ints);
        System.out.println(count);
    }
    public static int lengthOfLIS(int[] nums) {

        int[] dp = new int[nums.length];
        // 给所有的dp的元素填充值为 1
        Arrays.fill(dp,1);
        // 进行一个遍历
        int result=1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1); // 求其最大值
                }
            }
            result=Math.max(result,dp[i]);
        }

        return result;
    }


}
